// praktische informatik, aufgabe 1, written and composed by christian mayr

#include <list>
#include <vector>
#include <algorithm>
#include <stdio.h>

typedef std::list<unsigned> intlist;
typedef std::pair<unsigned, int> frontpair;
typedef std::vector<frontpair> pairvec;

intlist merge_lists(intlist *lists, unsigned k) 
{
    intlist merged;
    
    // construct heap from list elements, we store (value, list index) pairs
    pairvec front_elems(k);
    for (unsigned i = 0; i < k; ++i) 
	{
        front_elems[i] = frontpair(lists[i].front(), i);
        lists[i].pop_front();
    }

    std::make_heap(front_elems.begin(), front_elems.end());

    while (!front_elems.empty()) 
	{
        frontpair m = front_elems.front(); // get smallest element
        merged.push_back(m.first); // append to results
        std::pop_heap(front_elems.begin(), front_elems.end());
        front_elems.pop_back(); // remove element
        // fetch a new element from the list the smallest element came from
        if (!lists[m.second].empty()) 
		{
            front_elems.push_back(frontpair(lists[m.second].front(), m.second));
            lists[m.second].pop_front();
            std::push_heap(front_elems.begin(), front_elems.end());
        }
    }
    
    return merged;
}

void initListValues(intlist& list, unsigned* values, const unsigned size)
{
	for(unsigned i = 0; i < size; ++i)
		list.push_back(values[i]);
}

int main()
{
	intlist lists[4];

	unsigned values1[5] = {12, 9, 7, 5};
	unsigned values2[3] = {24, 14, 8};
	unsigned values3[5] = {45, 6, 4, 1, 0};
	unsigned values4[2] = {8, 2};

	initListValues(lists[0], values1, 5);
	initListValues(lists[1], values2, 3);
	initListValues(lists[2], values3, 5);
	initListValues(lists[3], values4, 2);

	intlist mergedList = merge_lists(lists, 4);

	printf("merged list:\n");
	for(intlist::iterator it = mergedList.begin(); it != mergedList.end(); ++it)
		printf("%u\n", *it);

	return 0;
}